The present disclosure relates to computing systems that employ caches. More particularly, the present disclosure relates to managing shared data, in a computing system, that can be stored in caches. The disclosure relates to data that can be cache lines of a memory, or alternative forms of data, such as data objects in a distributed computing system.
Processors in a computing system can employ local caches such as, for example, to improve access latency to instructions, and/or data, used by a processor (e.g., in executing instructions). However, a plurality of processors sharing data can lead to contention for that data among the processors. The contention can cause an increase in the frequency of transferring data between caches in various processors, particularly if one processor modifies a cache line shared by other processors, creating an incoherent data problem for the caches of the other processors and requiring the other processors to fetch a copy of the modified cache line. Increasing the frequency of transferring data, such as cache lines, can limit or reduce progress of a program, and/or increase the relative time spent transferring data, as opposed to using the data. Transferring cache lines between processors has an associated overhead (e.g., transfer latency, bus or inter-processor link utilization, etc.). A high, or increased, frequency of transferring data between processors correspondingly increases the associated overhead. The overhead can limit, or reduce, performance of processors and/or the overall computing system.
“A Low-Overhead Coherence Solution for Multiprocessors with Private Cache Memories”, by Mark S. Papamarcos and Janak H. Patel (hereinafter, “Papamarcos”), published Jan. 1, 1984 by the Institute of Electrical and Electronic Engineers (IEEE), describes effects of transferring cache lines between local caches of processors in a multiprocessor system. For example, Papamarcos describes a design for cache memory in multiprocessor systems comprising a “private cache for each processor, as shown in Fig. I” and that “this organization suffers from the well known data consistency, or cache coherence problem.” Papamarcos further states: “the simplest way to solve the coherence problem is to require that the address of the block being written in cache be transmitted throughout the system” but that “Obviously, the invalidate traffic grows very quickly”. Papamarcos describes a solution to reduce cache invalidation requests: “All unnecessary invalidate requests can be cut off at the point of origin. Bus traffic is therefore reduced to cache misses.”
While Papamarcos addresses overhead due to bus traffic associated with invalidation requests, a solution is still needed to address increased overhead associated with transferring cache lines subject to contention between contending processors, and particularly transferring cache lines subject to contention and associated with cache line misses.
Similar to processors sharing data, such as cache lines, applications executing in a computing system can employ caches, such as to improve access latency to a data object (e.g., a file, or a portion of an Internet page) used by the applications. However, shared data in a computing system can be subject to contention among the applications sharing that data, particularly if one application modifies the shared data and causes an incoherent data problem in the copies of the data held in the caches of other applications. The contention can cause an increase in the frequency of transferring data objects between various application caches, which can in turn increase overhead (e.g., transfer latency, network utilization, etc.) associated with caching data in the computing system. In a manner similar to processors sharing data, increased frequency of transferring data objects between applications can have a corresponding increase in overhead, which can in turn limit, or reduce, performance of the applications and/or the overall computing system.